package algorithmlearn.strmatch;

/**
 * 参考： https://blog.csdn.net/qq_28619473/article/details/88760101 这篇最后的代码理解有误，注意
 * https://wnjxyk.tech/2638.html
 */
public class KMPLearn {

    public static int KMP(String src, String target) {
        int i = 0;
        int j = 0;
        int[] next = getNext(target);
        while (i < src.length() && j < target.length()) {
            if (j == -1 || src.charAt(i) == target.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == target.length())
            return i - j;
        else
            return -1;
    }

    public static int[] getNext(String s) {
        /*int next[] = new int[s.length()];
        //起始化
        //pre_pmt为 -1 ；next数组next[0] 为 -1
        int j = 0;
        next[0] = -1;
        //从index 1 开始
        int i = 0;
        while(i<s.length()-1){
            if(j == -1 || s.charAt(i) == s.charAt(j)){
                //j == -1 表示延续上一轮的匹配next[i-1]最大长度，没能实现递增，继续从j=0对模式串前缀进行匹配
                //s.charAt(i) == s.charAt(j) 匹配成功，对 next[i]模式串前缀的最长前后缀 +1

                //前缀模式串比较位 +1
                j++;
                //主字符串比较位 +1
                i++;
                next[i] = j;

            }else {
                j=next[j];//一旦不匹配成功。J 一直回退到-1
                //j = -1;//其实就是回退到-1, 检查这样写也是正确的
            }
        }
        return next;*/
        int next[] = new int[s.length()];//定义大一个，防止越界，只有前length个数据有用
        int i=0;
        int j=-1; //求next数组的j 初始化为-1。这样设计是要使next[1]=0;
        next[0]=-1;
        //有越界就改这个地方 s.length()-1
        //这部分的循环就是字符串匹配  循环和上面很相似
        while(i<s.length()-1) {
            if(j==-1 || s.charAt(i)== s.charAt(j)) {
                next[i+1]=j+1;
                i++;
                j++;
            }else{
                //上一没能成功 例如【已 已 已 已 *n】 未
                //其实这里 结合 j==-1 来找【已 已 已 已 *n】的最长前后缀匹配项
                //然后 用 【已 *n】 最长前后缀匹配项 m + 未，来快速判断（这样就不用从头遍历【已 *n】，应为前面已经计算过next[j]，可以直接取 ）
                // ‘待匹配串’[m] 与 未 比较，不成功继续循环
                j=next[j];

                //要理解这块的含义
                //对“aabaaaa”的next[6]取值分析   ==-1 0 1 0 1 2 2
                //已知next[5] 为2，next[6]是对aabaaa进行 最长前后缀匹配项 计算为2；
                //过程
                // 1.首先在 i为5 next[5]的基础上尝试：：也就是 [aab]aaaa   与 aaba[aaa] 比较
                // 进行aabaaaa的j=2  b   与 aabaaaa的i=6  a比较;结果false
                // 2.j=next[j];   j = 1 ；；
                // 理解next[j]，因为上一步没能成功增加1 获取最长前后缀匹配项
                //所以要对aaba[aaa] ，去除一位，剩下【aa】与aabaaaa比较，
                // 对【aa】是否能取到最长前后缀匹配项，来快速进行，找到【aa】与aabaaaa比较结果
                // 为什么直接可以next数组的next[j] j=2，因为之前比较过  aabaa[aa]后缀 与 [aa]baaaa
                // #### ////重要理解这块 aabaa[aa]与[aa]baaaa 翻转 ；快速取 【aa】的最长前后缀匹配项，也就是之前的next[2]
                //  这里有一个循环  else  j=next[j] -》 j ！= -1  -》s.charAt(i)== s.charAt(j)
                // 【aa】的最长前后缀匹配项 其实等于   可以直接取[aa]baaaa 也就是next[2]  == 1
                // 3.进行aabaaaa的j=1  a   与 aabaaaa的i=5  a比较;结果true
                //返回 next[6] = 2
            }

        }
        return next;

    }

    public static void main(String[] args) {
        String src = "abaaabaaaabca";
        String target = "aabaaaa";
        /*String src = "qwertyuiopasdfghjklzxcvbnm";
        String target = "ghjklzxc";*/
        int next[]=getNext(target);
        for (int i : next) {
            System.out.print(i+" ");
        }

        System.out.println();
        System.out.println(KMP(src, target));
    }
}
